#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    string shortestPalindrome(string s) {
        string r = s;
        reverse(r.begin(), r.end());
        string s1 = " " + s + "#" + r;
        vector<int> next(s1.length(), 0);
        next[0] = -1;
        for (int i = 2, j = 0; i < s1.length(); i++) {
            while (j && s1[i] != s1[j + 1]) {
                j = next[j];
            }
            if (s1[i] == s1[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        return r.substr(0, r.length() - next[s1.length() - 1]) + s;
    }
};

int main() {
    Solution solution;
    string output = solution.shortestPalindrome("aacecaaa");
    cout << output << endl;
}